package com.cat.dynamicPlanning;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/zero-array-transformation-iv/
 * @create 2025/9/1 21:23
 * @since JDK17
 */

public class Solution40 {
    public int minZeroArray(int[] nums, int[][] queries) {
        int n = nums.length, m = queries.length, ans = 0;
        for (int i = 0; i < n; i++) {
            int x = nums[i];
            if (x == 0) {
                continue;
            }
            boolean[] dp = new boolean[x + 1];
            dp[0] = true;
            for (int k = 0; k < m; k++) {   // 执行k次操作
                var q = queries[k];
                if (i < q[0] || i > q[1]) {
                    continue;
                }
                var val = q[2];
                for (int j = x; j >= val; j--) {    // 减
                    dp[j] = dp[j] || dp[j - val];
                }
                if (dp[x]) {    // 已经到了
                    ans = Math.max(k + 1, ans);
                    break;
                }
            }
            if (dp[x] != true) {
                return -1;
            }
        }
        return ans;
    }
}
